package DFS;

import org.bouncycastle.util.Objects;
import org.junit.Assert;

import java.util.HashMap;
import java.util.Map;


public class Lee109 {
    public TreeNode sortedListToBST(ListNode head) {
        if (head == null) {
            return null;
        }

        return buildBST(head);
        // 关键就是找中点
    }

    private TreeNode buildBST(ListNode listNode){
        if(listNode == null){
            return null;
        }


        // 1 -> 2 -> 3 -> 4 -> 5 fast.next == null
        // 1 -> 2 -> 3 -> 4  fast.next.next = null
        // 1 -> 2

        // 找中点
        ListNode fast = listNode;
        ListNode slow = listNode;
        ListNode pre = null;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
            pre = (pre == null) ? slow : pre.next;
        }

        // 断开链表
        ListNode midListNode = slow;
        ListNode frontListNode;
        ListNode backListNode = slow.next;
        slow.next = null;

        if(pre == null){
            frontListNode = null;
        } else {
            frontListNode = listNode;
            pre.next = null;
        }

        // 构建链表
        TreeNode root = new TreeNode(midListNode.val);
        root.left = buildBST(frontListNode);
        root.right = buildBST(backListNode);

        return root;
    }
}
